package edu.cityu.cs.hk.datastructures;
import java.util.Comparator;
//begin#fragment SortedListPriorityQueue1
/** Implementation of a priority queue by means of a sorted list */
//end#fragment SortedListPriorityQueue1
/**
 * Realization of a priority queue by means of a sorted linked-list in
 * nondecreasing order.
 * @author Roberto Tamassia, Michael Goodrich, Eric Zamore
 */
//begin#fragment SortedListPriorityQueue1
public class SortedListPriorityQueue implements PriorityQueue {
  protected List L;
  protected Comparator c;
  protected Position actionPos; // variable used by subclasses
  /** Inner class for entries */
  protected static class MyEntry implements Entry {
    protected Object k; // key
    protected Object v; // value
    public MyEntry(Object key, Object value) {
      k = key;
      v = value;
    }
    // methods of the Entry interface
    public Object key() { return k; }
    public Object value() { return v; }
//end#fragment SortedListPriorityQueue1
    // overrides Object.toString, useful for debugging
    public String toString() { return "(" + k  + "," + v + ")"; }
//begin#fragment SortedListPriorityQueue1
  }
  /** Inner class for a default comparator using the natural ordering */
  protected static class DefaultComparator implements Comparator {
    public DefaultComparator() { /* default constructor */ }
    public int compare(Object a, Object b) throws ClassCastException { 
      return ((Comparable) a).compareTo(b);
    }
  }
  /** Creates the priority queue with the default comparator. */
  public SortedListPriorityQueue () {
    L = new NodeList();
    c = new DefaultComparator();
  }
  /** Creates the priority queue with the given comparator. */
  public SortedListPriorityQueue (Comparator comp) {
    L = new NodeList();
    c = comp;
  }
  //end#fragment SortedListPriorityQueue1
  /** Creates the priority queue with the given comparator and list.
   * The list is assumed to be sorted in nondecreasing order.*/
  public SortedListPriorityQueue (List list, Comparator comp) { 
    L = list;
    c = comp;
  }
  /** Sets the comparator for this priority queue.
   * @throws IllegalStateException if priority queue is not empty */
  public void setComparator(Comparator comp) throws IllegalStateException {
    if(!isEmpty())  // this is only allowed if the priority queue is empty
      throw new IllegalStateException("Priority queue is not empty");
    c = comp;
  }
  /** Returns the number of elements in the priority queue. */
  public int size () {return L.size(); }
  /** Returns whether the priority queue is empty. */
  public boolean isEmpty () { return L.isEmpty(); }
  //begin#fragment SortedListPriorityQueue2
  /** Returns but does not remove an entry with minimum key. */
  public Entry min () throws EmptyPriorityQueueException {
    if (L.isEmpty())
      throw new EmptyPriorityQueueException("priority queue is empty");
    else
      return (Entry) L.first().element();
  }
  /** Inserts a key-value pair and return the entry created. */
  public Entry insert (Object k, Object v) throws InvalidKeyException {
    checkKey(k); // auxiliary key-checking method (could throw exception)
    Entry entry = new MyEntry(k, v);
    insertEntry(entry); // auxiliary insertion method
    return entry;
  }
  /** Auxiliary method used for insertion. */
  protected void insertEntry(Entry e) {
    Object k = e.key();
    if (L.isEmpty()) {
      actionPos = L.insertFirst(e);	 // insert into empty list
    }
    else if (c.compare(k, key(L.last())) > 0) {
      actionPos = L.insertLast(e);	 // insert at the end of the list
    }
    else {
      Position curr = L.first();
      while (c.compare(k, key(curr))> 0) {
	curr = L.next(curr);		// advance toward insertion position
      }
      actionPos = L.insertBefore(curr, e); // useful for subclasses
    }
  }
  /** Removes and returns an entry with minimum key. */
  public Entry removeMin() throws EmptyPriorityQueueException {
    if (L.isEmpty())
      throw new EmptyPriorityQueueException("priority queue is empty");
    else
      return (Entry) (L.remove(L.first()));
  }
//end#fragment SortedListPriorityQueue2
  /** Returns the key stored at a given node. */
//begin#fragment SortedListPriorityQueue2
  protected Object key(Position pos) { return ((Entry) pos.element()).key(); }
//end#fragment SortedListPriorityQueue2

//begin#fragment SortedListPriorityQueue3
  /** Determines whether a key is valid. */
  protected boolean checkKey(Object key) throws InvalidKeyException {
    boolean result;
    try {		// check if the key can be compared to itself
      result = (c.compare(key,key)==0);
    } catch (ClassCastException e)
      {	throw new InvalidKeyException("key cannot be compared"); }
    return result;
  }
  // overrides Object.toString, useful for debugging
  public String toString() {
    return L.toString(); 
  }
//end#fragment SortedListPriorityQueue3
} 
